package com.mytest;

public class SortTest {
	public static void insertSort() {
		int array[] = { -1, 2, 4, 9, 5, -2, -8, 0 };
		int cur = 0, j = 0;
		for (int i = 1; i < array.length; i++) {
			cur = array[i];
			j = i - 1;
			while (j >= 0 && cur < array[j]) {
				array[j + 1] = array[j];
				j--;
			}
			array[j + 1] = cur;
		}
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ", ");
		}
	}

	public static void shellSort() {
		int cur = 0, j = 0;
		int[] data = new int[] { 5, 2, 8, 9, 1, 7, 6, 3, 4, 11, 15, 18 };
		System.out.println("初始数组(" + data.length + ")：");
		printArray(data);
		System.out.println("");
		for (int d = data.length / 2; d > 0; d = d / 2) {
			System.out.println("d; " + d);
			for (int i = d; i < data.length; i++) {
				cur = data[i];
				j = i - d;
				while (j >= 0 && cur < data[j]) {
					data[j + d] = data[j];
					j -= d;
				}
				data[j + d] = cur;
			}
			System.out.println("希尔排序后：");
			printArray(data);
		}
	}

	// --------------------------
	public static void quicksortMain() {
		int array[] = { 9, 5, 4, 8, 7, 3, 2, 10 };
		quicksort(array, 0, array.length - 1);
		printArray(array);
	}

	public static void quicksort(int n[], int left, int right) {
		int center = 0;
		if (left < right) {
			center = partition(n, left, right);
			quicksort(n, left, center - 1);
			quicksort(n, center + 1, right);
		}
	}

	public static int partition(int[] n, int left, int right) {
		int ctval = n[left];
		while (left < right) {
			while (left < right && n[right] > ctval)
				right--;
			n[left] = n[right];
			while (left < right && n[left] < ctval)
				left++;
			n[right] = n[left];
			n[left] = ctval;
		}
		return left;
	}

	// --------------------------
	public static void merge(int a[], int low, int ct, int high) {
		int length1 = ct - low + 1;
		int length2 = high - ct;
		int array1[] = new int[length1 + 1];
		int array2[] = new int[length2 + 1];
		for (int i = 0; i < length1; i++) {
			array1[i] = a[low + i];
		}
		for (int i = 0; i < length2; i++) {
			array2[i] = a[ct + i + 1];
		}
		array1[length1] = Integer.MAX_VALUE;
		array2[length2] = Integer.MAX_VALUE;
		int k1 = 0, k2 = 0;
		for(int i=low; i<=high; i++){
			if(array1[k1] <= array2[k2]){
				a[low++] = array1[k1];
				k1++;
			}else{
				a[low++] = array2[k2];
				k2++;
			}
		}
	}

	public static void mergeSort(int a[], int low, int high) {
		if (low == high) {
			return;
		}
		if (low < high) {
			int ct = (low + high) / 2;
			mergeSort(a, low, ct);
			mergeSort(a, ct + 1, high);
			merge(a, low, ct, high);
		}
	}

	public static void mergeSortTest() {
		int[] array = { 1, 3, 6, 4, 13, 14, 8, 12, 9, 7, 0 };
		mergeSort(array, 0, array.length - 1);
		printArray(array);
	}

	//=-------------------------------------------------------------------------------------------------------------------------------------------
	 // 排序函数=====================================================  
    public static void heapSort(int[] array) {  
        // 对数组进行筛选，建成一个大顶堆  
        double len = array.length - 1;  
        for (int i = (int) Math.floor(len / 2); i > 0; i--) {  
            heapAdjust(array, i, array.length - 1);  
        }  
        for (int i = array.length - 1; i > 1; i--) {  
            // 将堆顶元素与最后一个元素调换位置，即输出最大值  
            swap(array, 1, i);  
            // 将最后一位剔出，数组最大下标变为i-1。自队顶至叶子进行调整，形成一个新堆，此过程称为筛选  
            heapAdjust(array, 1, i - 1);  
        }  
    }  
  
    // 建堆函数，认为【s，m】中只有 s  
    // 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆=====================================================  
    public static void heapAdjust(int[] array, int s, int m) {  
        // 用0下标元素作为暂存单元  
        array[0] = array[s];  
        // 沿孩子较大的结点向下筛选  
        for (int j = 2 * s; j <= m; j *= 2) {  
            // 保证j为较大孩子结点的下标，j < m 保证 j+1 <= m ，不越界  
            if (j < m && array[j] < array[j + 1]) {  
                j++;  
            }  
            if (!(array[0] < array[j])) {  
                break;  
            }  
            // 若S位较小，应将较大孩子上移  
            array[s] = array[j];  
            // 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选  
            s = j;  
        }  
        // 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。。。  
        array[s] = array[0];  
    }  
  
    // 交换函数=====================================================  
    public static void swap(int[] array, int i, int j) {  
        int temp;  
        temp = array[i];  
        array[i] = array[j];  
        array[j] = temp;  
    }  
	
	public static void printArray(int[] array) {
		System.out.print("{");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]);
			if (i < array.length - 1) {
				System.out.print(", ");
			}
		}
		System.out.println("}");
	}

	public static void main(String[] args) {
		// 数组0下标元素作为暂存单元  
        int []array = {0,49,38,65,97,76,16,27,49,78,34,14,64,52,41,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
        heapSort(array);  
        printArray(array);
	}
}
